package leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Classname twoSum_0001
 * @Author happytaohaha
 * @Date 2020/2/29
 * @Description leetcode 第一题：两数之和  题目链接： https://leetcode-cn.com/problems/two-sum/
 * 思路：穷举法
 * 官方思路： 两遍hash和一遍hash
 */
public class TwoSum_0001 {

    /**
     * 穷举法：O(n^2)
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {
        int len = nums.length;
        for(int i = 0; i < len-1; i++){
            for(int j = i+1; j <len; j++){
                if(nums[i]+nums[j] == target){
                    return new int[]{i,j};
                }
            }
        }
        return null;
    }

    /**
     * 两遍hash 和一遍hash其实都一样  复杂度变为了O(n)
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum2(int[] nums, int target) {
        int len = nums.length;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i < len; i++){
           int result = target - nums[i];
           if(map.containsKey(result)){
               return new int[]{map.get(result),i};
           }
           map.put(nums[i],i);
        }
        return null;
    }






    public static void main(String[] args) {
        System.out.println(Arrays.toString(twoSum2(new int[]{2,7,11,15},9)));
    }
}
